package List.LinkList;

import java.util.Iterator;

public class LinkList<T> implements Iterable<T> {

    private class Node {
        private T item;
        private Node next;

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

    private Node head;//头节点
    private int N;//长度

    public LinkList() {
        //初始化头节点
        this.head = new Node(null, null);
        //初始化长度
        this.N = 0;
    }

    public void clear() {
        this.head = null;
        this.N = 0;
    }

    public int length() {
        return N;
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public T get(int index) {
        Node n = head.next;
        for (int i = 0; i < index; i++) {
            n = n.next;
        }
        return n.item;
    }

    public void insert(T t) {
        Node n = head;
        while (n.next != null) {
            n = n.next;
        }
        n.next = new Node(t, null);
        N++;
    }

    public void insert(int index, T t) {
        Node pre = head;
        if (index > N) {
            return;
        } else {
            for (int i = 0; i < index; i++) {
                pre = pre.next;
            }
            Node current = new Node(t, pre.next);
            pre.next = current;
            N++;
        }
    }

    public T remove(int index) {
        Node pre = head;
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }
        Node current = pre.next;
        pre.next = current.next;
        N--;
        return current.item;
    }

    public int indexOf(T t) {
        Node current = head;
        int i = 0;
        for (; current.next != null; i++) {
            current = current.next;
            if (current.item.equals(t)) {
                return i;
            }
        }
        //没找到，返回-1
        return -1;
    }

    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            private Node n = head;

            @Override
            public boolean hasNext() {
                return n.next != null;
            }

            @Override
            public T next() {
                n = n.next;
                return n.item;
            }
        };
    }

    /*  反转链表
        head -> 1 -> 2 -> 3 -> 4 -> null
        反转后为head -> 4 -> 3 -> 2 -> 1 -> null
        1.调用自定义方法reverse(Node n)反转每一个节点，从第一个开始
        2.如果发现n还有下一个节点，递归reverse(Node n.next)对下一个节点进行反转
        3.直到递归到最后一个元素，递归开始返回
     */
    public void reverse() {
        //如果当前链表为空直接结束
        if (isEmpty()) {
            return;
        }
        reverse(head.next);
    }

    public Node reverse(Node n) {
        if (n.next == null) {
            head.next = n;
            return n;
        }
        Node pre = reverse(n.next);
        pre.next = n;
        n.next = null;
        return n;
    }

    /*  快慢指针
        就是两个指针，一个走得快，一个走得慢，一般快指针的 step 为慢指针的 2 倍
     */
    //应用一：求链表中间节点
    public T getMid() {
        Node fast = head.next;
        Node slow = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow.item;
    }
    //应用二：单链表是否有环。当快指针等于慢指针就证明有环(快指针超了慢指针一圈)

}
